#ifndef BT_HASH_MAP_H
#define BT_HASH_MAP_H

#include "btAlignedObjectArray.h"

///very basic hashable string implementation, compatible with btHashMap
struct btHashString
{
    const char* m_string;
    unsigned int	m_hash;

    SIMD_FORCE_INLINE	unsigned int getHash()const
    {
        return m_hash;
    }

    btHashString(const char* name)
        : m_string(name)
    {
        /* magic numbers from http://www.isthe.com/chongo/tech/comp/fnv/ */
        static const unsigned int  InitialFNV = 2166136261;
        static const unsigned int FNVMultiple = 16777619;

        /* Fowler / Noll / Vo (FNV) Hash */
        unsigned int hash = InitialFNV;

        for (int i = 0; m_string[i]; i++)
        {
            hash = hash ^(m_string[i]);        /* xor  the low 8 bits */
            hash = hash * FNVMultiple;  /* multiply by the magic number */
        }
        m_hash = hash;
    }

    int portableStringCompare(const char* src,	const char* dst) const
    {
        int ret = 0 ;

        while (!(ret = *(unsigned char *)src - *(unsigned char *)dst) && *dst)
            ++src, ++dst;

        if (ret < 0)
            ret = -1 ;
        else if (ret > 0)
            ret = 1 ;

        return(ret);
    }

    const bool equals(const btHashString& other) const
    {
        return (m_string == other.m_string) ||
               (0 == portableStringCompare(m_string, other.m_string));

    }

};

const int BT_HASH_NULL = 0xffffffff;

template <class Value>
class btHashKey
{
    int	m_uid;
public:

    btHashKey(int uid)
        : m_uid(uid)
    {
    }

    int	getUid1() const
    {
        return m_uid;
    }

    bool equals(const btHashKey<Value>& other) const
    {
        return getUid1() == other.getUid1();
    }
    //to our success
    SIMD_FORCE_INLINE	unsigned int getHash()const
    {
        int key = m_uid;
        // Thomas Wang's hash
        key += ~(key << 15);
        key ^= (key >> 10);
        key += (key << 3);
        key ^= (key >> 6);
        key += ~(key << 11);
        key ^= (key >> 16);
        return key;
    }


};


template <class Value>
class btHashKeyPtr
{
    int	m_uid;
public:

    btHashKeyPtr(int uid)
        : m_uid(uid)
    {
    }

    int	getUid1() const
    {
        return m_uid;
    }

    bool equals(const btHashKeyPtr<Value>& other) const
    {
        return getUid1() == other.getUid1();
    }

    //to our success
    SIMD_FORCE_INLINE	unsigned int getHash()const
    {
        int key = m_uid;
        // Thomas Wang's hash
        key += ~(key << 15);
        key ^= (key >> 10);
        key += (key << 3);
        key ^= (key >> 6);
        key += ~(key << 11);
        key ^= (key >> 16);
        return key;
    }


};

///The btHashMap template class implements a generic and lightweight hashmap.
///A basic sample of how to use btHashMap is located in Demos\BasicDemo\main.cpp
template <class Key, class Value>
class btHashMap
{

    btAlignedObjectArray<int>		m_hashTable;
    btAlignedObjectArray<int>		m_next;

    btAlignedObjectArray<Value>		m_valueArray;
    btAlignedObjectArray<Key>		m_keyArray;

    void	growTables(const Key& key)
    {
        int newCapacity = m_valueArray.capacity();

        if (m_hashTable.size() < newCapacity)
        {
            //grow hashtable and next table
            int curHashtableSize = m_hashTable.size();

            m_hashTable.resize(newCapacity);
            m_next.resize(newCapacity);

            int i;

            for (i = 0; i < newCapacity; ++i)
            {
                m_hashTable[i] = BT_HASH_NULL;
            }
            for (i = 0; i < newCapacity; ++i)
            {
                m_next[i] = BT_HASH_NULL;
            }

            for (i = 0; i < curHashtableSize; i++)
            {
                //const Value& value = m_valueArray[i];
                //const Key& key = m_keyArray[i];

                int	hashValue = m_keyArray[i].getHash() & (m_valueArray.capacity() - 1);	// New hash value with new mask
                m_next[i] = m_hashTable[hashValue];
                m_hashTable[hashValue] = i;
            }


        }
    }

public:

    void insert(const Key& key, const Value& value)
    {
        int hash = key.getHash() & (m_valueArray.capacity() - 1);

        //replace value if the key is already there
        int index = findIndex(key);
        if (index != BT_HASH_NULL)
        {
            m_valueArray[index] = value;
            return;
        }

        int count = m_valueArray.size();
        int oldCapacity = m_valueArray.capacity();
        m_valueArray.push_back(value);
        m_keyArray.push_back(key);

        int newCapacity = m_valueArray.capacity();
        if (oldCapacity < newCapacity)
        {
            growTables(key);
            //hash with new capacity
            hash = key.getHash() & (m_valueArray.capacity() - 1);
        }
        m_next[count] = m_hashTable[hash];
        m_hashTable[hash] = count;
    }

    void remove(const Key& key)
    {

        int hash = key.getHash() & (m_valueArray.capacity() - 1);

        int pairIndex = findIndex(key);

        if (pairIndex == BT_HASH_NULL)
        {
            return;
        }

        // Remove the pair from the hash table.
        int index = m_hashTable[hash];
        btAssert(index != BT_HASH_NULL);

        int previous = BT_HASH_NULL;
        while (index != pairIndex)
        {
            previous = index;
            index = m_next[index];
        }

        if (previous != BT_HASH_NULL)
        {
            btAssert(m_next[previous] == pairIndex);
            m_next[previous] = m_next[pairIndex];
        }
        else
        {
            m_hashTable[hash] = m_next[pairIndex];
        }

        // We now move the last pair into spot of the
        // pair being removed. We need to fix the hash
        // table indices to support the move.

        int lastPairIndex = m_valueArray.size() - 1;

        // If the removed pair is the last pair, we are done.
        if (lastPairIndex == pairIndex)
        {
            m_valueArray.pop_back();
            m_keyArray.pop_back();
            return;
        }

        // Remove the last pair from the hash table.
        const Value* lastValue = &m_valueArray[lastPairIndex];
        int lastHash = m_keyArray[lastPairIndex].getHash() & (m_valueArray.capacity() - 1);

        index = m_hashTable[lastHash];
        btAssert(index != BT_HASH_NULL);

        previous = BT_HASH_NULL;
        while (index != lastPairIndex)
        {
            previous = index;
            index = m_next[index];
        }

        if (previous != BT_HASH_NULL)
        {
            btAssert(m_next[previous] == lastPairIndex);
            m_next[previous] = m_next[lastPairIndex];
        }
        else
        {
            m_hashTable[lastHash] = m_next[lastPairIndex];
        }

        // Copy the last pair into the remove pair's spot.
        m_valueArray[pairIndex] = m_valueArray[lastPairIndex];
        m_keyArray[pairIndex] = m_keyArray[lastPairIndex];

        // Insert the last pair into the hash table
        m_next[pairIndex] = m_hashTable[lastHash];
        m_hashTable[lastHash] = pairIndex;

        m_valueArray.pop_back();
        m_keyArray.pop_back();

    }


    int size() const
    {
        return m_valueArray.size();
    }

    const Value* getAtIndex(int index) const
    {
        btAssert(index < m_valueArray.size());

        return &m_valueArray[index];
    }

    Value* getAtIndex(int index)
    {
        btAssert(index < m_valueArray.size());

        return &m_valueArray[index];
    }

    Value* operator[](const Key& key)
    {
        return find(key);
    }

    const Value*	find(const Key& key) const
    {
        int index = findIndex(key);
        if (index == BT_HASH_NULL)
        {
            return NULL;
        }
        return &m_valueArray[index];
    }

    Value*	find(const Key& key)
    {
        int index = findIndex(key);
        if (index == BT_HASH_NULL)
        {
            return NULL;
        }
        return &m_valueArray[index];
    }


    int	findIndex(const Key& key) const
    {
        unsigned int hash = key.getHash() & (m_valueArray.capacity() - 1);

        if (hash >= (unsigned int)m_hashTable.size())
        {
            return BT_HASH_NULL;
        }

        int index = m_hashTable[hash];
        while ((index != BT_HASH_NULL) && key.equals(m_keyArray[index]) == false)
        {
            index = m_next[index];
        }
        return index;
    }

    void	clear()
    {
        m_hashTable.clear();
        m_next.clear();
        m_valueArray.clear();
        m_keyArray.clear();
    }

};

#endif //BT_HASH_MAP_H
